/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package uk.ac.cam.can.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import uk.ac.cam.can.Data;
import uk.ac.cam.can.evaluation.Evaluation;
import uk.ac.cam.can.misc.MathTools;

/**
 *
 * @author Thomas
 */
public class KAnon {    
    protected Data data;
    protected int k;
    
    protected double d;
    private int oSize;
    List<PosGen[]> results = new ArrayList<PosGen[]>();
    PosGen[] best = null;
    private long executionTime;
    
    
    
    public KAnon(Data data, int k, double d){
        this.data=data;
        data.load();
        data.getRecords();
        this.k=k;
        this.d=d;
        data.load();
        this.oSize=data.size();
    }
    
    protected PosGen[][] getAttributesGeneralisationHierarchy(){
        PosGen[][] p = new PosGen[data.nbAttributes()][];
        for(int i = 0; i < data.nbAttributes(); i++){
            p[i] = new PosGen[data.getMaxGeneralisation(i)];
            for(int j = 0; j < p[i].length; j++){
                p[i][j]=new PosGen(i, j);
            }
        }
        return p;
    }
    
    public void findBest(){
        long start = System.nanoTime();
        PosGen[][] p = this.getAttributesGeneralisationHierarchy();
        
        List<PosGen[]> output = new ArrayList<PosGen[]>();
        permutation(p, 0, new ArrayList<PosGen>(), output);
        
        
        PosGen[][] cmbs = new PosGen[output.size()][];
        for(int i = 0; i < cmbs.length; i++){            
            cmbs[i]=output.get(i);
        }
        
        for(PosGen[] cmb : cmbs){
            boolean isAnon=true;
            for(int i = 1; i <= p.length; i++){
                isAnon&=combinationTest(cmb, i);
                if(!isAnon)
                    break;
            }
            if(isAnon){
                boolean isGeneralisation=false;
                for(PosGen[] candidate : results){
                    if(isGeneralisation(cmb, candidate)){
                        isGeneralisation=true;
                    }
                }
                if(!isGeneralisation)
                    results.add(cmb);
            }
        }
        
        double minQual = Double.MAX_VALUE;
        int minCost = Integer.MAX_VALUE;
        for(PosGen[] cmb : results){
            data.load();
            isAnonymous(cmb);
            double quality = Evaluation.computeQuality(data);
            if(quality<minQual){
                minQual=quality;
                best=cmb;
            }
        }
        // keep that for
        isAnonymous(best);
        executionTime = ((System.nanoTime()-start)/1000000000);
    }
    
    private boolean isGeneralisation(PosGen[] toBeCompared, PosGen[] cmb){
        for(PosGen c : cmb){
            boolean res=false;
            for(PosGen comp : toBeCompared){
                if(c.position()==comp.position()){
                    if(comp.generalisation()>=c.generalisation()){
                        res=true;
                        break;
                    }
                }
            }
            if(!res)
                return false;
        }
        return true;
    }
    
    public void printResult(){
        /*
        String tmp = "";
        for(PosGen[] cmb : results){
            if(!tmp.contains(getSignificative(cmb, data.getNbQuasi())))
                tmp+=getSignificative(cmb, data.getNbQuasi())+"\n";
        }
        System.out.println(tmp);
        System.out.print("Best candidate:");*/
        System.out.println(getSignificative(best, data.getNbQuasi()));
        isAnonymous(best);
        System.out.println("Anonymisation: "+executionTime+"s");
        System.out.println("Quality : "+Evaluation.computeQuality(data)+" / "+Evaluation.computeWorstQuality(data));
        System.out.println("Risk : "+Evaluation.computeRisk(data));
    }
    
    protected int getMaxCost(){
        return data.getMaxCost();
    }
    
    protected int computeCost(PosGen[] cmb){
        int c=0;
        for(PosGen pg : cmb){
            c += pg.generalisation()* data.getCost(pg.position());
        }
        return c;
    }
    
    public void dumpRecord(String[] record){
        for(String a : record)
            System.out.print(a+" ");
        System.out.println();
    }
    
    protected void permutation(PosGen[][] inputs, int index, List<PosGen> tmp, List<PosGen[]> output){        
        if(index == inputs.length){
            PosGen[] v = new PosGen[inputs.length];
            for(int i=0; i < tmp.size(); i++){
                v[i]=tmp.get(i);
            }
            output.add(v);
        }else{
            for(int i=0 ; i<inputs[index].length ; i++){
                tmp.add(inputs[index][i]);
                permutation(inputs,index+1,tmp, output);
                tmp.remove(tmp.size() - 1); 
            }
        }
    }
    
    
    
    private boolean combinationTest(PosGen[] input, int nbElement){
        int[] subset = new int[nbElement];
        for(int i = 0; i < subset.length; i++){
            subset[i]=i;
        }
        
        int totCombination = MathTools.factorial(input.length) / (MathTools.factorial(nbElement)*MathTools.factorial(input.length-nbElement));
        boolean result=true;
        for(int i = totCombination; i > 0; i--){
            if(i!=totCombination){
                int x = nbElement-1;
                while(subset[x]==input.length-nbElement+x){
                    x--;
                }
                subset[x]=subset[x]+1;
                for(int j=x+1; j < nbElement; j++){
                    subset[j]=subset[x]+j-x;
                }
            }
            int p = 0;
            PosGen[] comb = new PosGen[nbElement];
            for(int j=0; j < nbElement; j++){
                comb[p]=input[subset[j]];
                p++;
            }
            result &= check(comb);
            
        }
        return result;
    }
    
    
    protected Map<String, Boolean> pruneResults = new HashMap<String, Boolean>();
    private boolean check(PosGen[] combination){
        String tmp="";
        for(PosGen pg : combination)
            tmp+=pg.toString();
        
        if(pruneResults.containsKey(tmp)){            
            return pruneResults.get(tmp);
        }else{
            if(!isAnonymous(combination)){
                pruneResults.put(tmp, false);
                return false;
            }else{
                mark(combination);
                return true;
            }
        }
    }
    
    protected void mark(PosGen[] cmb){
        PosGen[][] hierarchy = new PosGen[cmb.length][];
        for(int i = 0; i < hierarchy.length; i++){
            int nb = data.getMaxGeneralisation(cmb[i].position()) - cmb[i].generalisation();
            hierarchy[i]=new PosGen[nb];
            for(int j = 0; j < nb; j++){
                hierarchy[i][j]= new PosGen(cmb[i].position(), cmb[i].generalisation()+j);
            }
        }
        
        List<PosGen[]> output = new ArrayList<PosGen[]>();
        permutation(hierarchy, 0, new ArrayList<PosGen>(), output);
        for(PosGen[] cmbs : output){
            String tmp="";
            for(PosGen pg : cmbs)
                tmp+=pg.toString();
            pruneResults.put(tmp, true);
        }
    }
    
    public boolean isAnonymous(PosGen[] combination){
        data.load();
        // apply anonymisation level as defined by the set
        for(PosGen pg : combination){
                data.generalise(pg.position(), pg.generalisation());
        }
        
        // build the q groups
        Map<String, List<String[]>> qgroups = new HashMap<String, List<String[]>>();
        for(String[] record : data.getRecords()){
            String qi="";
            for(PosGen pg : combination){
                if(data.getType(pg.position())==Data.TYPE_QUASI_IDENTIFIER)
                    qi+=record[pg.position()];
            }
            if(qi.equals(""))
                return true;
            if(qgroups.containsKey(qi)){
                qgroups.get(qi).add(record);
            }else{
                //System.out.println(qi);
                qgroups.put(qi, new ArrayList<String[]>());
                qgroups.get(qi).add(record);
            }            
        }
        
        // verify the qgroups meet the criteria
        for(List<String[]> qgroup : qgroups.values()){
            if(!criteria(combination, qgroup)){
                data.removeAll(qgroup);
            }
        }
        return testDeletion();
    }
    
    protected boolean testDeletion(){
        if(data.size()==0)
            return false;
        //System.out.println((oSize-data.size())+" patients deleted");
        int deleted = oSize-data.size();
        if(deleted > (int)(oSize*d))
            return false;
        return true;
    }
    
    protected boolean criteria(PosGen[] combination, List<String[]> qgroup){        
        if(qgroup.size() < k)
            return false;
        else 
            return true;
    }
    
    
    
    public void dump(PosGen[] pgs){
       for(PosGen pg : pgs){
           System.out.print(pg+" ");
       }
       System.out.println(computeCost(pgs));
    }
    
    public String getSignificative(PosGen[] pgs, int s){
       int i = 0;
       String line="";
       for(PosGen pg : pgs){
           if(i++>=s)
               break;
           line+=pg.generalisation()+" ";
       }
       return line;
    }
    
    public void saveBest(String fileName) throws Exception{
        isAnonymous(best);
        data.save(fileName);
    }
}
